/**
 * 带头结点的队列的链式存储
 */

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

//链式队列结点
typedef struct LinkNode{
	int data;
	struct LinkNode* next;
}LinkNode;

//队列的队头和队尾
typedef struct {
	LinkNode* front;
	LinkNode* rear;
}*LinkQueue;

//队列初始化
void initQueue(LinkQueue &queue);

//判断队列是否为空
bool isEmpty(LinkQueue &queue);

//入队
bool inQueue(LinkQueue &queue, int data);

//出队
int outQueue(LinkQueue &queue);

//遍历当前队列中的元素
void print(LinkQueue &queue);
int main()
{
	LinkQueue queue;
	initQueue(queue);
	inQueue(queue,1);
	inQueue(queue,2);
	printf("===%d\n",queue->front->data);
	inQueue(queue,3);
	inQueue(queue,4);
	inQueue(queue,5);
	inQueue(queue,6);
	printf("%d\n",outQueue(queue));
	printf("%d\n",outQueue(queue));
	printf("%d\n",outQueue(queue));
	printf("%d\n",outQueue(queue));
	printf("%d\n",outQueue(queue));
	return 0;
}

void initQueue(LinkQueue &queue)
{
	queue->front=(LinkNode* )malloc(sizeof(LinkNode));
	queue->rear=queue->front;
	if(!queue->front) return;
	queue->front->next=NULL;
}

bool isEmpty(LinkQueue &queue)
{
	return queue->front==queue->rear ? true : false;
}

bool inQueue(LinkQueue &queue, int data)
{
	LinkNode* newLinkNode=(LinkNode* )malloc(sizeof(LinkNode));
	if(!newLinkNode) return false;
	newLinkNode->data=data;
	newLinkNode->next=NULL;
	queue->rear->next=newLinkNode;
	queue->rear=newLinkNode;
	return true;
}

int outQueue(LinkQueue &queue)
{
	//判断队列是否为空
	if(isEmpty(queue)) return -1;
	//returnNode结点是返回结点
	LinkNode* node=queue->front->next;
	int data=node->data;
	//queue->front重新建立连接
	queue->front->next=node->next;
	//如果队列中只有一个结点,删除后queue->front=queue->rear
	if(queue->rear==node) queue->front=queue->rear;
	free(node);
	printf("data:%d\n",data);
	return data;	
}

void print(LinkQueue &queue)
{
	if(isEmpty(queue)) return;
	LinkQueue tmpQueue=queue;
	while(tmpQueue->front!=queue->rear)
	{
		printf("%d ",tmpQueue->front->data);
		tmpQueue->front=tmpQueue->front->next;
	}
	printf("\n");
}